#define _CRT_SECURE_NO_WARNINGS   1


typedef char StackType;
typedef struct Stack {
    StackType* a;
    int top;
    int capacity;
}Stack;

void StackInit(Stack* st) {
    st->a = NULL;
    st->top = 0;
    st->capacity = 0;

}
void StackInsert(Stack* st, StackType val)
{
    if (st->top == st->capacity)
    {
        int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
        st->a = (StackType*)realloc(st->a, newcapacity * sizeof(StackType));
        st->capacity = newcapacity;

    }
    st->a[st->top++] = val;
}

void StackPop(Stack* st)
{
    if (st->top > 0)
        st->top--;


}
bool StackEmpty(Stack* st)
{
    return st->top == 0;;

}




bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    while (*s)
    {
        if (*s == '(' || *s == '{' || *s == '[')
        {
            StackInsert(&st, *s);
            s++;
        }
        else if (StackEmpty(&st))
            return false;
        else if (st.a[st.top - 1] == '(' && *s != ')' || st.a[st.top - 1] == '[' && *s != ']' || st.a[st.top - 1] == '{' && *s != '}')
            return false;
        else
        {
            s++;
            StackPop(&st);
        }



    }
    if (!StackEmpty(&st))
    {
        return false;
    }
    if (st.capacity != 0)
    {
        free(st.a);
    }
    return true;


}